﻿#define _CRT_SECURE_NO_WARNINGS 1
//不相邻取数
//运用的也是: 01背包的思想（动态规划）
//方法一：
//#include <iostream>
//using namespace std;
//
//const int N = 100010;
//int a[N];
//long long f[N];
//int n;
//
//int main() 
//{
//    cin >> n;
//    for (int i = 1; i <= n; i++) 
//    {
//        cin >> a[i];
//    }
//
//    f[0] = 0, f[1] = a[1];
//    for (int i = 2; i <= n; i++) 
//    {
//        f[i] = max(a[i] + f[i - 2], f[i - 1]);
//    }
//
//    printf("%lld", f[n]);
//    return 0;
//}
//
//方法二：可能比较难思考
// dp[i][0] 为不取第i个数的情况下，前i个数不相邻取数的最大值；
// dp[i][1] 为取第i个数的情况下，前i个数不相邻取数的最大值。那么有转移方程：
//不取当前数，那么前一个数取不取都行：
//即：dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]);
//若取当前数，那么前一个数一定不能取：
//即：dp[i][1] = dp[i - 1][0] + a[i];
//#include <iostream>
//#include <algorithm>
//using namespace std;
//long long a[101010], dp[101010][2];
//int main() 
//{
//    int n, i;
//    cin >> n;
//    for (i = 1; i <= n; i++)cin >> a[i];
//    for (i = 1; i <= n; i++) 
//    {
//        dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]);
//        dp[i][1] = dp[i - 1][0] + a[i];
//    }
//    cout << max(dp[n][0], dp[n][1]);
//}


//#include <iostream>
//#include <vector>
//#include <algorithm>
//using namespace std;
//
//int main()
//{
//    int n = 0, p = 0;
//    int maxcount = 1, count = 1, sum = 0;
//    vector<vector<int>> k;
//    vector<int> v;
//    cin >> n >> p;
//    v.resize(n + 1, 0);
//    k.resize(n + 1);
//    for (int i = 1; i < n + 1; i++)
//    {
//        cin >> v[i];
//        k[i].resize(2);
//        k[i][0] = v[i] - p;
//        k[i][1] = v[i] + p;
//    }
//    //计数
//    sort(k.begin(), k.end());
//    sum = k[1].back();
//    for (int i = 2; i < n + 1; i++)
//    {
//        if (k[i].front() <= sum)
//        {
//            count++;
//            sum = min(k[i].back(), sum);
//        }
//        else
//        {
//            maxcount = max(maxcount, count);
//            count = 1;
//            sum = k[i].back();
//        }
//    }
//    maxcount = max(maxcount, count);
//    cout << maxcount << endl;
//    return 0;
//}


//#include <iostream>
//#include <string>
//#include <algorithm>
//using namespace std;
//
//bool IsStr(string& str, int left, int right)
//{
//    while (left < right)
//    {
//        if (str[left] != str[right])
//        {
//            return false;
//        }
//        left++;
//        right--;
//    }
//    return true;
//}
//int main()
//{
//    int minlength = 110;
//    string str;
//    cin >> str;
//    for (int i = 0; i < str.size(); i++)
//    {
//        for (int j = i + 1; j < str.size(); j++)
//        {
//            if (IsStr(str, i, j))
//            {
//                minlength = min(minlength, j - i + 1);
//                break;
//            }
//        }
//    }
//    if (minlength == 110)
//    {
//        cout << -1 << endl;
//    }
//    else
//    {
//        cout << minlength << endl;
//    }
//    return 0;
//}
//
